package com.yinxin.wudasuanfa.huaweiod;

/**
 * @author yinxin
 * @version 1.0
 * @Description: 求一个数组子集乘积小于k的集合个数
 * @date 2022/5/517:41
 */
public class Exercise5 {

   public static void main(String[] args) {
      int[] nums = {1,2,3,5,7};
      //int[] nums = {1,2,3};
      int k = 15;
      int res = numSubarrayProductLessThanK(nums, k);
      System.out.println(res);
   }

   public static int numSubarrayProductLessThanK(int[] nums, int k) {
      if (k == 0){
         return 0;
      }
      int product = 1, j = 0, ret = 0;
      for (int i = 0; i < nums.length; i++){
         product *= nums[i];
         j++;
         if (product < k){
            ret += j;
         } else{
            while (product >= k && j > 0){
               product /= nums[i - j-- + 1];
            }
            ret += j;
         }
      }
      return ret;
   }

}
